import java.util.HashMap;
import java.util.Map;
import java.util.Set;

class Solution {

    public String minWindow(String s, String t) {
        // 返回最小子串
        int len = t.length();
        // 记录t
        Map<Character,Integer> tMap = new HashMap<>();
        for(char c : t.toCharArray()) {
            tMap.put(c,tMap.getOrDefault(c,0) +1);
        }
        Map<Character,Integer> cur = new HashMap<>();
        int left = 0,right =0;
        int start = 0,end = Integer.MAX_VALUE;
        while(right < s.length()) {
            char c = s.charAt(right);
            cur.put(c,cur.getOrDefault(c,0) + 1);
            while(right-left +1 >= len) {
                if(!match(cur,tMap)) {
                    break;
                }
                // 匹配
                if(right-left < end-start) {
                    start= left;
                    end = right;
                }
                // left ++
                char removeC = s.charAt(left++);
                cur.put(removeC,cur.get(removeC) -1);
            }
            right++;
        }
        return s.substring(start,end+1);
    }

    private boolean match(Map<Character,Integer> cur,Map<Character,Integer> tMap) {
        Set<Character> keys = tMap.keySet();
        for(char key : keys) {
            if(!cur.containsKey(key)) {
                return false;
            }
            int tval = tMap.get(key);
            int curVal = cur.get(key);
            if(curVal < tval) {
                return false;
            }
        }
        return true;
    }
}